1. Field of the Invention
This invention relates generally to data processing systems and, more particularly, to data processing systems that have a plurality of central processing units using the techniques of virtual addressing to interact with a main memory unit.
2. Discussion of the Related Art
In the modern data processing system, a hierarchical memory system is typically used. The bulk of the data capable of being accessed by a data processing system is stored on mass storage media such as magnetic tape, magnetic disks or other media capable of storing large amounts of digital information. These media are typically too slow to permit the direct addressing of the stored data by a central processing unit. A memory unit, generally referred to as the main memory unit, is implemented with a faster technology and stores portions of the data required by the data processing system. (Although not directly related to the present invention, a memory of yet faster technology utilized for storing data of immediate importance to the central processing unit and physically located within the central processing unit is generally included in the data processing system. The memory apparatus in the central processing unit is referred to as the buffer or cache memory.)
Each central processing unit or processor, by means of the operating system, has access to all of the available data associated with the data processing system and can utilize this data as required. As a practical matter, because of the size of data available to the processor, the retrieval of the required data from the mass storage devices would have a detrimental impact on the performance of the process execution. The data having an immediate requirement by the data processing system is stored in the main memory unit. Because storing all of the data in the main memory is impractical, the data is divided into data blocks, called pages, that are entered into the main memory unit as separate entities.
In the virtual memory techniques, at the start of operation of the data processing unit, the operating system allocates the space available in the main memory unit. Main memory unit space will be allocated to programs, tables, and portions of the operating system required for the operation of the data processing system. This space in the main memory unit does not have the contents replaced as is typical of the remainder of the data stored in the main memory unit. The remainder of the main memory unit is divided in equal blocks where groups of related data signals that are important to the data processing system can be stored. These data signal blocks are referred to as page frames. Associated with each page frame is a group of data signals in a table of related signals referred to as the page frame descriptor. The operating system can reference the page frame descriptor and the page frame descriptor identifies or points to the location of the associated page descriptor. The page description includes information relating the virtual or symbolic address manipulated by the processors of a data processing system to the actual or physical address where the original information is stored. Also associated with each page descriptor are signals relating to status information. The page frame descriptor also includes data signals in a location referred to as a linker, the linker being indicative of the order of the page frames according to a preselected algorithm defining how order of the page frames is to be defined.
After initialization of the data processing system, a processor will require a group of data signals. A software procedure will provide the information relating the physical address to the symbolic address for the required group of data signals. The information relating these quantities is stored in the page descriptor. The appropriate information is entered in the linker portion of the page frame descriptor indicating that this is the first of the sequence of page frames. As additional page frames are added, the linker information will identify the order of the page frames in the sequence. After the page frames are all occupied with data, a processor will continue to require access to new data, requiring that a page frame already containing data will have new data replace the old data. It is implementation of this page frame data replacement to which the present invention is related.
From the linker information, the next possible page frame in the sequence of page frames can be determined. Based on the linker information, the page description associated with that page frame can be identified and the page descriptor can be entered in the processor. The processor, under software control in the prior art, examines the values of the status signals in the page descriptor and, based on the values of these status signals, a decision is made as to the whether data in that page frame can be replaced. For example, a status signal that is frequently used relates to the experience that the optimum strategy for the replacement of data is to replace the least most recently used data. To implement the least most recently used strategy requires an unacceptable amount of processing overhead. A typical strategy is to remove the "data used" signal according to a predetermined procedure, and to set the "data used" in the page descriptor whenever the data associated with a page frame is used. In this manner, the software procedures can determine that the data has been used within a preselected period of time.
In addition, still other status signals can be associated with the page frame. Because of the multiplicity of status signals, a software procedure providing a decision with respect to the replacement of the associated group of data can be complex and require an unacceptable amount of processing activity.
When the program controlling the operation of the data processing system requires data signal groups not currently stored in the main memory unit, the replacement algorithm is invoked. In the prior art, the replacement algorithm was executed by a software process, requiring an analysis of the several status signals. During the determination of the page frame data to be replaced, access to the descriptor was prevented to prevent the use of data that could be in the process of change. One technique to prevent access during this period of possible data change was to provide the portions of the main memory unit space with a memory "lock", the memory lock preventing access to the main memory unit or the selected portions thereof. This technique was effective in insuring that proper data was used by the processors, but, because of the relative slow execution of the software replacement algorithm, the performance of the entire data processing system could be severely impacted. As will be clear to those skilled in the art, for practical reasons, the memory lock typically involves a plurality of memory location groups or pages. The performance of the data processing system will therefore be impacted even if the particular location being analyzed by the replacement algorithm is not accessed.
In order to eliminate the reservation of a main memory portion during execution of the replacement algorithm, techniques have been used that permit the execution of the replacement without reservation of the main memory unit portion. According to this technique, a determination is made, after a replacement page frame selection has been performed for a particular location, if a change has occurred in the status signals of the page frame header during the execution of the replacement algorithm. This technique has required additional complexity in the data processing system.
A need has therefore been felt for a technique that permits the determination of a main memory unit location suitable for having the present data stored therein replaced by new data required by the data processing system.
OBJECTS OF THE INVENTION
It is an object of the present invention to provide an improved data processing system.
It is a feature of the present invention to provide for a replacement of a group of data in the main memory of a data processing system according to preselected criteria based on status signals associated with the group of data.
It is another feature of the present invention to provide for an analysis of a group of status signals without using a software procedure for the analysis.